package 练习;

import algs4.In;

import java.util.*;
import java.util.function.BiFunction;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 三数之和
 * 功能概要  :
 *
 * @Author : yangwk
 * @Date : 2024/3/15 22:50
 */
public class 三数之和 {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{0, 2, 2, 3, 0, 1, 2, 3, -1, -4, 2}));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        return threeSum(nums, 0);
    }

    public static List<List<Integer>> threeSum(int[] arr, int target) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (i > 0 && arr[i - 1] == arr[i]) {
                continue;
            }
            List<List<Integer>> integers = twoSum(arr, i + 1, target - arr[i]);
            if (!integers.isEmpty()) {
                result.addAll(integers);
            }
        }
        return result;
    }

    public static List<List<Integer>> twoSum(int[] arr, int start, int target) {
        Map<Integer, Boolean> set = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();
        for (int i = start; i < arr.length; i++) {
            int val = arr[i];
            if (set.containsKey(target - val)) {
                if (!set.get(target - val)) {
                    ArrayList<Integer> objects = new ArrayList<>();
                    objects.add(val);
                    objects.add(target - val);
                    objects.add(arr[start - 1]);
                    result.add(objects);
                    set.put(target - val, true);
                    set.put(val, true);
                }
            }else{
                set.put(val, false);
            }
        }
        return result;
    }
}
